#include <string>

#include "common/exception.h"
#include "common/logger.h"
#include "common/rid.h"
#include "storage/index/b_plus_tree.h"
#include "storage/page/header_page.h"

namespace bustub {
INDEX_TEMPLATE_ARGUMENTS
BPLUSTREE_TYPE::BPlusTree(std::string name, BufferPoolManager *buffer_pool_manager, const KeyComparator &comparator,
                          int leaf_max_size, int internal_max_size)
    : index_name_(std::move(name)),
      root_page_id_(INVALID_PAGE_ID),
      buffer_pool_manager_(buffer_pool_manager),
      comparator_(comparator),
      leaf_max_size_(leaf_max_size),
      internal_max_size_(internal_max_size) {}

/*
 * Helper function to decide whether current b+tree is empty
 */
INDEX_TEMPLATE_ARGUMENTS
auto BPLUSTREE_TYPE::IsEmpty() const -> bool { 
  if(this->root_page_id_==INVALID_PAGE_ID)
    return true; 
  return false;
}
/*****************************************************************************
 * SEARCH
 *****************************************************************************/
/*
 * Return the only value that associated with input key
 * This method is used for point query
 * @return : true means key exists
 */

INDEX_TEMPLATE_ARGUMENTS
auto BPLUSTREE_TYPE::GetValue(const KeyType &key, std::vector<ValueType> *result, Transaction *transaction) -> bool {
  auto value = this->Find(key,transaction);
  if(value.GetPageId()<0)
    return false;
  result->push_back(value);
  return true;
}


INDEX_TEMPLATE_ARGUMENTS
auto BPLUSTREE_TYPE::SplitNode(LeafPage *&oldLeaf,LeafPage *&newLeaf,const KeyType& key,const ValueType& value)->MappingType{
  MappingType *tempMemory = new MappingType[oldLeaf->GetMaxSize()];
  oldLeaf->CopyToTemp(tempMemory);
  int i;
  for(i=0;i<oldLeaf->GetSize();i++){
    if(this->comparator_(key,tempMemory[i].first)==-1){//如果要插入的数据小于当前的值，就把数据插入这里，此处的数据往后移动
      break;
    }
  }
  for(int j=oldLeaf->GetMaxSize();j>i;j--){
    tempMemory[j] = tempMemory[j-1];
  }
  tempMemory[i].first = key;
  tempMemory[i].second = value;
  //将数据插入正确的位置
  //创建新的页面
  page_id_t pageid = newLeaf->GetPageId();
  (void)pageid;
  newLeaf->SetNextPageId(oldLeaf->GetNextPageId());//新的页面指向原来页面的下一个兄弟
  oldLeaf->SetNextPageId(newLeaf->GetPageId());//原来的页面指向新的页面
  oldLeaf->Erase();//清楚原来的页面

  //将tempMemory分别复制到两页中
  for(int i=1;i<oldLeaf->GetMaxSize()/2;i++){
    oldLeaf->SetKeyAt(tempMemory[i].first,i);
    oldLeaf->SetValueAt(tempMemory[i].second,i);
  }
  for(int i=oldLeaf->GetMaxSize()/2;i<oldLeaf->GetMaxSize();i++){//中间节点是否要加入还是直接放到父节点 // 还是从n/2处开始复制
    newLeaf->SetKeyAt(tempMemory[i].first,i);
    newLeaf->SetValueAt(tempMemory[i].second,i);
  }
  MappingType midData = tempMemory[oldLeaf->GetMaxSize()/2];
  delete tempMemory;
  return midData;
}


INDEX_TEMPLATE_ARGUMENTS
auto BPLUSTREE_TYPE::SplitNode(InternalPage *&oldInternal,InternalPage *&newInternal,const KeyType& key,const page_id_t& value)->std::pair<KeyType,page_id_t>{
  auto *tempMemory = new std::pair<KeyType,page_id_t>[oldInternal->GetMaxSize()+1];//非叶子节点，大小为n，能够存储n-1个key，但是有n个value，所以当非叶子节点满了的时候
  oldInternal->CopyToTemp(tempMemory);//将第一个value也复制进去                     //如果想要继续存储，需要分配n+1个节点
  int i;
  for(i=1;i<oldInternal->GetMaxSize();i++){//从下标为1的开始比较，如果比1小，则插在这个位置上，插入的节点不可能比当前非叶子节点的第一个没有key的value还靠前
    if(this->comparator_(key,tempMemory[i].first)==-1){//如果要插入的数据小于当前的值，就把数据插入这里，此处的数据往后移动，注意是GetMaxSize，不是GetSize()
      break;
    }
  }
  for(int j=oldInternal->GetMaxSize();j>i;j--){
    tempMemory[j] = tempMemory[j-1];
  }
  tempMemory[i].first = key;
  tempMemory[i].second = value;
  //将数据插入正确的位置
  //创建新的页面
  page_id_t pageid = newInternal->GetPageId();
  (void)pageid;
  oldInternal->Erase();//清楚原来的页面，注意，清楚完之后，第一个value已经没了
  int j=1;
  //将tempMemory分别复制到两页中
  oldInternal->SetValueAt(tempMemory[0].second,0);
  reinterpret_cast<BPlusTreePage*>(this->buffer_pool_manager_->FetchPage(tempMemory[i].second)->GetData())->SetParentPageId(oldInternal->GetPageId());
  for(i=1;i<(oldInternal->GetMaxSize()+1)/2;i++){//从1开始，没有考虑value
    oldInternal->SetKeyAt(tempMemory[i].first,i);
    oldInternal->SetValueAt(tempMemory[i].second,i);
    reinterpret_cast<BPlusTreePage*>(this->buffer_pool_manager_->FetchPage(tempMemory[i].second)->GetData())->SetParentPageId(oldInternal->GetPageId());
    oldInternal->IncreaseSize(1);
  }
  //此时i=oldInternal->GetMaxSize()/2
  newInternal->SetValueAt(tempMemory[i].second,0);//将中间节点的value存下来
  reinterpret_cast<BPlusTreePage*>(this->buffer_pool_manager_->FetchPage(tempMemory[i].second)->GetData())->SetParentPageId(newInternal->GetPageId());
  auto midData = tempMemory[i];//但是中间节点的key要向上升

  for(i=(oldInternal->GetMaxSize()+1)/2+1;i<oldInternal->GetMaxSize()+1;i++,j++){//剩余的节点依次复制进page
    newInternal->SetKeyAt(tempMemory[i].first,j);
    newInternal->SetValueAt(tempMemory[i].second,j);
    reinterpret_cast<BPlusTreePage*>(this->buffer_pool_manager_->FetchPage(tempMemory[i].second)->GetData())->SetParentPageId(newInternal->GetPageId());
    newInternal->IncreaseSize(1);
  }
  
  //现在将这段unpin放到插入之后，即等到newInternal和oldInternal都不用之后才unpin
  // this->buffer_pool_manager_->UnpinPage(newInternal->GetPageId(),true);//可能这里有问题，在buffer少的时候
  // this->buffer_pool_manager_->UnpinPage(oldInternal->GetPageId(),true);  
  delete tempMemory;
  return midData;
}

// 注意：key是比较大小的索引，value是page_id
INDEX_TEMPLATE_ARGUMENTS

auto BPLUSTREE_TYPE::FindLeaf(const KeyType &key, Transaction *transaction) -> BPlusTreePage *{
  BPlusTreePage *root = reinterpret_cast<BPlusTreePage *>(this->buffer_pool_manager_->FetchPage(this->root_page_id_)->GetData());
  page_id_t childPageId;
  int32_t idx;
  while(!root->IsLeafPage()){ // 中间节点
    InternalPage* interpage = reinterpret_cast<InternalPage*>(root);

    //在上面实现寻找最小的比key大的值
    idx = interpage->SearchKey(key,this->comparator_);
    if(idx < 0){ //异常
      std::cout<<"error: [ idx < 0 ] and key is "<<key.ToString()<<"file: "<<__FILE__<<" line: "<<__LINE__<<std::endl;
      abort();
      return nullptr;
    }
    KeyType idxKey = interpage->KeyAt(idx);
    if(this->comparator_(key,idxKey)==1){ // 待插入的key比idx的值还大，需要往下找，即将当前页面节点最后一个key指向的page取出来，还是走右边
      childPageId = interpage->ValueAt(idx);
    }else if(this->comparator_(key,idxKey)==0){//相等 ，则走右边
      childPageId = interpage->ValueAt(idx);
    }else{ //比查找到的小，走左边
      childPageId = interpage->ValueAt(idx-1);
    }
    root = reinterpret_cast<BPlusTreePage *>(this->buffer_pool_manager_->FetchPage(childPageId)->GetData());
  }
  return root;
}


INDEX_TEMPLATE_ARGUMENTS
auto BPLUSTREE_TYPE::Find(const KeyType &key,Transaction *transaction) -> ValueType{
  auto root = this->FindLeaf(key,transaction);
  if(!root){//如果为空
    std::cout<<"leaf is null"<<std::endl;
    return RID(-1,0);
  }
  //叶子节点
  if(root->IsLeafPage()){
    LeafPage *leaf = reinterpret_cast<LeafPage*>(root);
    int32_t idx = leaf->SearchKey(key,this->comparator_);
    if(idx<0)
      return RID(-1,0);
    RID value = leaf->ValueAt(idx);
    return value;
  }
  std::cout<<"leaf is error"<<std::endl;
  return RID(-1,0);
}

INDEX_TEMPLATE_ARGUMENTS
auto BPLUSTREE_TYPE::FindBegin() ->  LeafPage *{
  BPlusTreePage *root = reinterpret_cast<BPlusTreePage *>(this->buffer_pool_manager_->FetchPage(this->root_page_id_)->GetData());
  page_id_t childPageId;
  // int32_t idx;
  while(!root->IsLeafPage()){ // 中间节点
    InternalPage* interpage = reinterpret_cast<InternalPage*>(root);
    childPageId = interpage->ValueAt(0);
    root = reinterpret_cast<BPlusTreePage *>(this->buffer_pool_manager_->FetchPage(childPageId)->GetData());
  }
  return reinterpret_cast<LeafPage*>(root);
}


INDEX_TEMPLATE_ARGUMENTS
auto BPLUSTREE_TYPE::FindEnd() ->  LeafPage *{
  BPlusTreePage *root = reinterpret_cast<BPlusTreePage *>(this->buffer_pool_manager_->FetchPage(this->root_page_id_)->GetData());
  page_id_t childPageId;
  // int32_t idx;
  while(!root->IsLeafPage()){ // 中间节点
    InternalPage* interpage = reinterpret_cast<InternalPage*>(root);
    childPageId = interpage->ValueAt(interpage->GetSize());
    root = reinterpret_cast<BPlusTreePage *>(this->buffer_pool_manager_->FetchPage(childPageId)->GetData());
  }
  return reinterpret_cast<LeafPage*>(root);
}
/*****************************************************************************
 * INSERTION
 *****************************************************************************/
/*
 * Insert constant key & value pair into b+ tree
 * if current tree is empty, start new tree, update root page id and insert
 * entry, otherwise insert into leaf page.
 * @return: since we only support unique key, if user try to insert duplicate
 * keys return false, otherwise return true.
 */

//TODO 抽取函数

INDEX_TEMPLATE_ARGUMENTS
auto BPLUSTREE_TYPE::Insert_in_leaf(LeafPage*& page,const KeyType &key, const ValueType &value, Transaction *transaction)  ->bool{
  if(page->GetSize()==0){
    page->SetKeyAt(key,0);
    page->SetValueAt(value,0);
    page->IncreaseSize(1);
    this->buffer_pool_manager_->UnpinPage(page->GetPageId(),true);
    return true;
  }
  if(this->comparator_(key,page->KeyAt(0))==-1){//如果小于第一个值(idx=0)，就直接插入第一个位置
    for(int i=page->GetSize();i>=1;i--){
      page->SetKeyAt(page->KeyAt(i-1),i);// 没有重载 =  ,可能出问题
      page->SetValueAt(page->ValueAt(i-1),i);
    }
    page->SetKeyAt(key,0);
    page->SetValueAt(value,0);
    page->IncreaseSize(1);
    this->buffer_pool_manager_->UnpinPage(page->GetPageId(),true);
    return true;
  }else{
    int i;
    for(i=0;i<page->GetSize();i++){//向后移动，将指定的key插入位置
      if(this->comparator_(key,page->KeyAt(i))==-1){//之前将下面的for放到if里面，
        break;                                      //如果待插入的位置在最后，就没办法执行了
      }
    }
    for(int j=page->GetSize();j>i;j--){
      page->SetKeyAt(page->KeyAt(i-1),i);// 跟上面重复，后面抽取成一个函数
      page->SetValueAt(page->ValueAt(i-1),i);
    }
    page->SetKeyAt(key,i);
    page->SetValueAt(value,i);
    page->IncreaseSize(1);
    this->buffer_pool_manager_->UnpinPage(page->GetPageId(),true);
    return true;
  }
  return false;
}


INDEX_TEMPLATE_ARGUMENTS
auto BPLUSTREE_TYPE::Insert_in_parent( BPlusTreePage* oldPage, BPlusTreePage* newPage, const KeyType &key,Transaction *transaction) ->bool{
  if(oldPage->IsRootPage()){//之前分裂的页面已经是root了，就创建新的root,可能还需要设置parentid
    page_id_t rootid;
    InternalPage* root = reinterpret_cast<InternalPage*>(this->buffer_pool_manager_->NewPage(&rootid)->GetData());//可能需要init
    root->Init(rootid,rootid,this->internal_max_size_);
    this->root_page_id_ = rootid;
    root->SetKeyAt(key,1);
    root->IncreaseSize(1);//别忘了加一
    //这里可能不能直接调用原来的oldPage，因为oldPage现在执行的内存已经没有了，因为缓存不够大，此时将oldPage给释放了，但是现在新的页面重新占据了这片缓存
    //所以此时oldPage指向的内存地址应该跟root一样
    /*
    gdb
    p root    ->  0x5555556ed138
    p oldPage ->  0x5555556ed138
    因为只是把内存槽中的page换出去，槽的地址不变，但是内容已经变了
    这种情况只存在于Newpage时发现buffer不够
    */
    root->SetValueAt(oldPage->GetPageId(),0);//根节点设置左右两个孩子节点
    root->SetValueAt(newPage->GetPageId(),1);
    oldPage->SetParentPageId(rootid);//设置父节点id
    newPage->SetParentPageId(rootid);
    this->UpdateRootPageId(1);
    this->buffer_pool_manager_->UnpinPage(rootid,true);//文档中写着，在对任何页面写或者读之后，需要unpin
    return true;
  }else{
    //获取parent // 注意，这里需要调整顺序
    InternalPage* parentPage = reinterpret_cast<InternalPage*>(this->buffer_pool_manager_->FetchPage(oldPage->GetParentPageId())->GetData());
    if(parentPage->GetSize()<parentPage->GetMaxSize()-1){//internalPage的node可以还可以继续存数据，注意
    //注意根据测试结果来看，非叶子节点也只能存储n-1个
      int i=1,j;
      for(;i<parentPage->GetSize()+1;i++){
        if(this->comparator_(key,parentPage->KeyAt(i))==-1){
          break;
        }
      }//不是直接插在后面，还是需要选择位置插入
      for(j=parentPage->GetSize()+1;j>i;j--){
        parentPage->SetKeyAt(parentPage->KeyAt(j-1),j);
        parentPage->SetValueAt(parentPage->ValueAt(j-1),j);
      }
      parentPage->SetKeyAt(key,i);
      parentPage->SetValueAt(newPage->GetPageId(),i);
      // parentPage->SetKeyAt(key,parentPage->GetSize()+1);
      // parentPage->SetValueAt(newPage->GetPageId(),parentPage->GetSize()+1);
      newPage->SetParentPageId(parentPage->GetPageId());//设置新页面的父节点id
      parentPage->IncreaseSize(1);//别忘了加一
      this->buffer_pool_manager_->UnpinPage(parentPage->GetPageId(),true);
      return true;
    }else{ //父节点也插满了，分裂父节点
      page_id_t newParentPageId;
      InternalPage* newParentPage = reinterpret_cast<InternalPage*>(this->buffer_pool_manager_->NewPage(&newParentPageId)->GetData());
      newParentPage->Init(newParentPageId,parentPage->GetParentPageId(),this->internal_max_size_);
      auto needToInsert = this->SplitNode(parentPage,newParentPage,key,newPage->GetPageId());//注意修改之后的pageid，因为在此处的pageid和后面new的pageid重复了
      Insert_in_parent(parentPage,newParentPage,needToInsert.first);
      this->buffer_pool_manager_->UnpinPage(newParentPage->GetPageId(),true);//可能这里有问题，在buffer少的时候
      this->buffer_pool_manager_->UnpinPage(parentPage->GetPageId(),true);
      return true;
    }
  }

  return false;
}

INDEX_TEMPLATE_ARGUMENTS
auto BPLUSTREE_TYPE::Insert(const KeyType &key, const ValueType &value, Transaction *transaction) -> bool {
  LeafPage* leaf;
  if(this->IsEmpty()==true){
    page_id_t page_id;
    leaf = reinterpret_cast<LeafPage*>(this->buffer_pool_manager_->NewPage(&page_id)->GetData());
    if(leaf==nullptr){
      std::cout<<"pages all in use"<<std::endl;
      return false;
    }
    this->root_page_id_ = page_id;
    leaf->Init(page_id,page_id,this->leaf_max_size_); // 如果parentid等于当前页面id就是root
  }else{
    leaf = reinterpret_cast<LeafPage*>(this->FindLeaf(key,transaction));
  }

  if(leaf->GetSize()<leaf->GetMaxSize()-1){//还能继续插入数据
    this->Insert_in_leaf(leaf,key,value,transaction);
    this->buffer_pool_manager_->UnpinPage(leaf->GetPageId(),true);
    this->UpdateRootPageId(1);
    return true;
  }else{//已经满了
    MappingType *tempMemory = new MappingType[leaf->GetMaxSize()];
    leaf->CopyToTemp(tempMemory);
    int i;
    for(i=0;i<leaf->GetSize();i++){
      if(this->comparator_(key,tempMemory[i].first)==-1){//如果要插入的数据小于当前的值，就把数据插入这里，此处的数据往后移动
        break;
      }
    }
    for(int j=leaf->GetMaxSize()-1;j>i;j--){//存n个，最后一个从n-1开始
      tempMemory[j] = tempMemory[j-1];
    }
    tempMemory[i].first = key;
    tempMemory[i].second = value;
    //将数据插入正确的位置
    //创建新的页面
    page_id_t pageid;
    LeafPage* newLeaf = reinterpret_cast<LeafPage*>(this->buffer_pool_manager_->NewPage(&pageid));
    newLeaf->Init(pageid,leaf->GetParentPageId(),this->leaf_max_size_);
    
    newLeaf->SetNextPageId(leaf->GetNextPageId());//新的页面指向原来页面的下一个兄弟
    leaf->SetNextPageId(newLeaf->GetPageId());//原来的页面指向新的页面
    leaf->Erase();//清楚原来的页面

    //将tempMemory分别复制到两页中
    for(int i=0;i<leaf->GetMaxSize()/2;i++){
      leaf->SetKeyAt(tempMemory[i].first,i);
      leaf->SetValueAt(tempMemory[i].second,i);
      leaf->IncreaseSize(1);//注意要加一
    }
    for(int j=leaf->GetMaxSize()/2,i=0;j<leaf->GetMaxSize();i++,j++){
      newLeaf->SetKeyAt(tempMemory[j].first,i);
      newLeaf->SetValueAt(tempMemory[j].second,i);
      newLeaf->IncreaseSize(1);//注意要加一
    }
    auto needToInsert = std::pair<KeyType,int32_t>(tempMemory[leaf->GetMaxSize()/2].first,tempMemory[leaf->GetMaxSize()/2].second.GetPageId());
    this->Insert_in_parent(leaf,newLeaf,needToInsert.first);
    // this->buffer_pool_manager_->UnpinPage(leaf->GetPageId(),true);
    // this->buffer_pool_manager_->UnpinPage(newLeaf->GetPageId(),true);
    this->UpdateRootPageId(1);
    return true;  
  }
  return false;
}

/*****************************************************************************
 * REMOVE
 *****************************************************************************/
/*
 * Delete key & value pair associated with input key
 * If current tree is empty, return immdiately.
 * If not, User needs to first find the right leaf page as deletion target, then
 * delete entry from leaf page. Remember to deal with redistribute or merge if
 * necessary.
 */

INDEX_TEMPLATE_ARGUMENTS
void BPLUSTREE_TYPE::deleteImpl(BPlusTreePage* page ,const KeyType &key, Transaction *transaction){
  if(page->IsRootPage()){//此处的判断是否还剩一个孩子节点有问题，暂时先设置程如果size为0，就替换程自己的孩子节点
  //已经将一个节点删除了，如果现在还剩一个，且当前节点为root，只剩一个child，即kv只剩一个，对于非叶子节点为0，对于叶子节点为1
    if(page->GetPageType()==IndexPageType::LEAF_PAGE&&page->GetSize()==1){//叶子节点
//直接返回
    }else if(page->GetPageType()==IndexPageType::INTERNAL_PAGE&&page->GetSize()==0){//非叶子节点
      //最好对非叶子节点的删除做特殊处理，如果只剩两个子节点，删除一个之后，剩下的放在0的位置
      //创建叶子节点，将剩下的节点放进去，充当root节点
      //不能简单的将不要的根节点删除就好了，除了重新设置根节点，还要将原始根节点连接的子节点对应的父节点id修改
      InternalPage* inter = reinterpret_cast<InternalPage*>(page);
      page_id_t page_id = inter->ValueAt(0);
      this->SetRootPageId(page_id);//将root的左孩子设置成root
      //将左孩子，即现在的根节点的父节点设置成page_id
      BPlusTreePage* leftChild = reinterpret_cast<BPlusTreePage*>(this->buffer_pool_manager_->FetchPage(page_id)->GetData());
      leftChild->SetParentPageId(page_id);

      this->buffer_pool_manager_->DeletePage(page->GetPageId());//删除父节点
    }
  }else if(page->GetSize()<page->GetMinSize()){
    page_id_t parentPageId = page->GetParentPageId();//11.2 此处可能由于之前删除页面之后使得parent page id改变或者之前的page已经被销毁但是还没有修改
    InternalPage* parentPage = reinterpret_cast<InternalPage*>(this->buffer_pool_manager_->FetchPage(parentPageId)->GetData());
    int i;
    for( i=0;i<parentPage->GetSize();i++){//查询当前page在parentPage中对应的位置
      if(parentPage->ValueAt(i)==page->GetPageId())
        break;
    }
    BPlusTreePage* newPage;
    page_id_t id;
    int32_t idx,internodeid; //idx表示另一个页面的编号,internodeid表示中间节点的编号，这里的编号为parentpage中数据的下标
    if(i==0){ // 如果是第一个节点的，只能找后面的孩子节点
      idx=1;
      internodeid=1;
    }else{// 如果是后面的节点，就找前一个孩子节点
      idx=i-1;
      internodeid = i;
    }
    auto InterNodeKey = parentPage->KeyAt(internodeid);//两个孩子页面之间的key，value,分别表示key和对应的页面id
    auto InterNodeValue = parentPage->ValueAt(internodeid);

    id = parentPage->ValueAt(idx); // 父节点是internal page，所以valaue是int
    //获取另一个孩子页面，page id，从而获取对应页面数据
    newPage = reinterpret_cast<BPlusTreePage*>(this->buffer_pool_manager_->FetchPage(id)->GetData());
    int maxsize = page->GetMaxSize()-1;

    int sum=page->GetSize()+newPage->GetSize();
    if(!newPage->IsLeafPage()){
      sum++;
    }
    
    //11.2 更新，判断是否可以放进一个节点的方法有问题，叶子节点直接计算相加小于等于，非叶子节点，如果想要
    //将右边的整体移动到左边，需要考虑右边还有一个没有key的第一个元素，如果两个相加小于等于，就可以
    if(sum<=maxsize){//如果两个页面能放到一个新的页面里面
      int j,k;
      if(i<idx){//idx表示的是另一个页面的索引，而i表示当前页面的索引
        BPlusTreePage* temp;
        temp=newPage;
        newPage = page;
        page=temp;
      }
      if(!page->IsLeafPage()){//11.2 如果不是leaf，需要将父节点中的中间值复制过去，并将右边页面的值复制过去
        InternalPage* internalpage = reinterpret_cast<InternalPage*>(page);
        InternalPage* internalNewPage = reinterpret_cast<InternalPage*>(newPage);
        j = internalNewPage->GetSize()+1;//出现internalNewPage->GetSize() ==0 出现bug，因为上面交换页面指针,需要设置如果父节点的size变为0之后，如果append，从1开始插入

        internalNewPage->SetKeyAt(InterNodeKey,j);//先把父节点中的中间节点插入，即把key先插入，再将右边节点的所有值都移动到左边
        (void)(InterNodeValue);

        internalNewPage->SetValueAt(internalpage->ValueAt(0),j);
        //先把右边节点的第一个无key的值移动过去，接着循环移动剩下的，后面的k从1开始，注意，移动完页面之后要把父节点修改
        BPlusTreePage* chailPage = reinterpret_cast<BPlusTreePage*>(this->buffer_pool_manager_->FetchPage(internalpage->ValueAt(0))->GetData());
        chailPage->SetParentPageId(internalNewPage->GetPageId());

        //增加完之后才是1，所以j还是得从2开始
        internalNewPage->IncreaseSize(1);

        //再将右边页面的数据进行复制 一开始j为0，就从1开始，后面就正常放，因为j为1的时候，放入一个，也增加了一个，所以从下标为2的开始
        for(j=internalNewPage->GetSize()+1,k=1;k<=internalpage->GetSize();j++,k++){//internalPage从1开始放置，而leafPage从0开始防止
          internalNewPage->SetKeyAt(internalpage->KeyAt(k),j);        // 注意这里的k和j的关系确定没有问题++++
          internalNewPage->SetValueAt(internalpage->ValueAt(k),j);
          internalNewPage->IncreaseSize(1);

          //还需要将value所对应的page的parent id修改
          //此操作只有非叶子节点需要，因为叶子节点的移动直接移动的是数据，没有父节点
          //但是非叶子节点移动的是指向下面子节点的指针，子节点需要更新父节点
          BPlusTreePage* chailPage = reinterpret_cast<BPlusTreePage*>(this->buffer_pool_manager_->FetchPage(internalpage->ValueAt(k))->GetData());
          chailPage->SetParentPageId(internalNewPage->GetPageId());
        }
        //需要更新父节点指针
        // std::cout<<"temp "<<std::endl;

      }else{//11.2 如果是leaf，直接复制过去，并更改nextpageid
      //page指向后一个页面，newPage指向前一个页面
        LeafPage *leafpage = reinterpret_cast<LeafPage*>(page);
        LeafPage *leafNewPage = reinterpret_cast<LeafPage*>(newPage);//page指向的是后面的节点，newPage指向的是前面的节点
        for(j=leafNewPage->GetSize(),k=0;k<leafpage->GetSize();j++,k++){
          leafNewPage->SetKeyAt(leafpage->KeyAt(k),j);
          leafNewPage->SetValueAt(leafpage->ValueAt(k),j);
          leafNewPage->IncreaseSize(1);
        }
        leafNewPage->SetNextPageId(leafpage->GetNextPageId());
      }

      delete_entry(parentPage,InterNodeKey,transaction);//向上调整leafnewPage
      this->buffer_pool_manager_->DeletePage(page->GetPageId());//删除page
    }else{//一页放不下
      if(idx<i){//另一个页面在原来页面的前面，即原来页面不是第一个，向左借一个  TODO
        if(!page->IsLeafPage()){//不是leaf节点
          InternalPage* internalpage = reinterpret_cast<InternalPage*>(page);//右边的页面
          InternalPage* internalNewPage = reinterpret_cast<InternalPage*>(newPage);//左边的页面
          page_id_t NewPageLastValue = internalNewPage->ValueAt(internalNewPage->GetSize());
          auto NewPageLastKey = internalNewPage->KeyAt(internalNewPage->GetSize());
          // internalNewPage->DeleteKV(NewPageLastKey,this->comparator_);
          //直接将internalNewPage 的size减一即可
          internalNewPage->IncreaseSize(-1);
          
          //非leaf节点的第一个位置，只有value没有key，向左边页面接一个节点过来，需要将父节点的key作为当前leaf的第一个位置的key，
          //此时所有节点都使用了，整体向后移动并将左边接过来的value作为第一个位置的value，而左边借过来的的key作为父节点的key

          internalpage->SetKeyAt(InterNodeKey,0);//右边先将第一个位置原本没有key的位置填上key，再一起往后移动，再在空出的第一个位置将value填上
          for(int k=internalpage->GetSize()+1;k>0;k--){//11.2 注意 GetSize对于internalpage是刚好最后一个，对应着下标。所以往后移动需要GetSize+1
            internalpage->SetKeyAt(internalpage->KeyAt(k-1),k);
            internalpage->SetValueAt(internalpage->ValueAt(k-1),k);
          }
          internalpage->IncreaseSize(1);//因为从父节点增加了一个key，所以在移动完之后需要加一

          internalpage->SetValueAt(NewPageLastValue,0);//设置第一个节点的指针
          parentPage->SetKeyAt(NewPageLastKey,internodeid);//将父节点的key设置成原始的左边的最后一个key，相当于将左边的key向上移动，将父节点的key挤下去
          //由于将左边的value移动过来了，所以需要将移动的节点的父节点值进行更新

          InternalPage* changeParentPage =  reinterpret_cast<InternalPage*>(this->buffer_pool_manager_->FetchPage(NewPageLastValue)->GetData());
          changeParentPage->SetParentPageId(internalpage->GetPageId());
          
        }else{
          LeafPage *leafpage = reinterpret_cast<LeafPage*>(page);
          LeafPage *leafNewPage = reinterpret_cast<LeafPage*>(newPage);

          auto NewPageLastValue = leafNewPage->ValueAt(leafNewPage->GetSize());
          auto NewPageLastKey = leafNewPage->KeyAt(leafNewPage->GetSize());
          
          leafNewPage->IncreaseSize(-1);
          
          //leaf节点，向左边页面接一个节点过来，
          //需要将父节点的key作为当前leaf的第一个位置的key，此时所有节点都使用了，整体向后移动
          //并将左边接过来的value作为第一个位置的value，而左边借过来的的key作为父节点的key，
          for(int k=leafpage->GetSize();k>0;k--){
            leafpage->SetKeyAt(leafpage->KeyAt(k-1),k);
            leafpage->SetValueAt(leafpage->ValueAt(k-1),k);
          }
          leafpage->SetKeyAt(InterNodeKey,0);//设置第一个节点的key
          leafpage->SetValueAt(NewPageLastValue,0);//设置第一个节点的指针

          parentPage->SetKeyAt(NewPageLastKey,internodeid);
          //将父节点的key设置程左边的最后一个key
          //相当于将左边的key向上移动，将父节点的key挤下去
        }
      }else{
        //11.2 向右借一个节点，下面的是11.2 修改完的
        if(!page->IsLeafPage()){//不是leaf节点
          InternalPage* internalpage = reinterpret_cast<InternalPage*>(page);
          InternalPage* internalNewPage = reinterpret_cast<InternalPage*>(newPage);
          
          page_id_t NewPageFirstValue = internalNewPage->ValueAt(0);
          auto NewPageFirstKey = internalNewPage->KeyAt(1);
          //11.2更改
          // internalNewPage->DeleteKV(NewPageLastKey);  有问题不能这么写
          //前面节点借用的时候，设置最后一个节点，key为父节点的key，值为右边页面的0号value
          //注意，如果internalpage->GetSize()等于0，则需要在1的位置插入，如果不是0，比如当前为1，但是因为第一个位置不放东西
          //所以1的位置是存放值的，所以要在2的位置放，所以internalpage->GetSize()需要加1，存放东西
          internalpage->SetKeyAt(InterNodeKey,internalpage->GetSize()+1);//父节点的中间节点
          internalpage->SetValueAt(NewPageFirstValue,internalpage->GetSize()+1);
          
          //借用完加一       11.2 TODO 被借用的节点是否减一了
          internalpage->IncreaseSize(1);
          
          //将移动过去的value所指向的父节点进行修改
          InternalPage* changeParentPage =  reinterpret_cast<InternalPage*>(this->buffer_pool_manager_->FetchPage(NewPageFirstValue)->GetData());
          changeParentPage->SetParentPageId(internalpage->GetPageId());

          //更改父节点中的的key，其子节点不需要更改
          parentPage->SetKeyAt(NewPageFirstKey,internodeid);

          //将右边页面调整程符合条件的形状//调整的时候有问题
          internalNewPage->SetValueAt(internalNewPage->ValueAt(1),0);
          internalNewPage->SetSize(internalNewPage->GetSize()-1);
          for(int k=1;k<=internalNewPage->GetSize();k++){
            internalNewPage->SetKeyAt(internalNewPage->KeyAt(k+1),k);
            internalNewPage->SetValueAt(internalNewPage->ValueAt(k+1),k);
          }

        }else{//TODO 可能需要像上的一样要修改
          LeafPage *leafpage = reinterpret_cast<LeafPage*>(page);
          LeafPage *leafNewPage = reinterpret_cast<LeafPage*>(newPage);

          auto NewPageFirstValue = leafNewPage->ValueAt(0);
          auto NewPageFirstKey = leafNewPage->KeyAt(0);

          //前面节点借用的时候，设置最后一个节点，key为父节点的key，值为右边页面的0号value
          leafpage->SetKeyAt(InterNodeKey,leafpage->GetSize());
          leafpage->SetValueAt(NewPageFirstValue,leafpage->GetSize());
          //借用完加一
          leafpage->IncreaseSize(1);
          //更改父节点的key
          parentPage->SetKeyAt(NewPageFirstKey,internodeid);

          //将右边页面调整程符合条件的形状
          for(int k=0;k<leafNewPage->GetSize();k++){
            leafNewPage->SetKeyAt(leafNewPage->KeyAt(k+1),k);
            leafNewPage->SetValueAt(leafNewPage->ValueAt(k+1),k);
          }
        }
      }
    }
  }
}

INDEX_TEMPLATE_ARGUMENTS
void BPLUSTREE_TYPE::delete_entry(LeafPage* leaf ,const KeyType &key, Transaction *transaction){
  leaf->DeleteKV(key,this->comparator_);
  deleteImpl(leaf,key,transaction);
}
INDEX_TEMPLATE_ARGUMENTS
void BPLUSTREE_TYPE::delete_entry(InternalPage* internal ,const KeyType &key, Transaction *transaction){
  internal->DeleteKV(key,this->comparator_);
  deleteImpl(internal,key,transaction);
}


INDEX_TEMPLATE_ARGUMENTS
void BPLUSTREE_TYPE::Remove(const KeyType &key, Transaction *transaction) {
  LeafPage* leaf = reinterpret_cast<LeafPage*>(this->FindLeaf(key,transaction));
  delete_entry(leaf,key,transaction);
}

/*****************************************************************************
 * INDEX ITERATOR
 *****************************************************************************/
/*
 * Input parameter is void, find the leaftmost leaf page first, then construct
 * index iterator
 * @return : index iterator
 */
INDEX_TEMPLATE_ARGUMENTS
auto BPLUSTREE_TYPE::Begin() -> INDEXITERATOR_TYPE { 
  LeafPage* left = this->FindBegin();
  return INDEXITERATOR_TYPE(left,this->buffer_pool_manager_,0); 
}

/*
 * Input parameter is low key, find the leaf page that contains the input key
 * first, then construct index iterator
 * @return : index iterator
 */
INDEX_TEMPLATE_ARGUMENTS
auto BPLUSTREE_TYPE::Begin(const KeyType &key) -> INDEXITERATOR_TYPE { 
  LeafPage* leaf = reinterpret_cast<LeafPage*>(this->FindLeaf(key));
  int32_t idx = leaf->SearchKey(key,this->comparator_);
  return INDEXITERATOR_TYPE(leaf,this->buffer_pool_manager_,idx); 
}

/*
 * Input parameter is void, construct an index iterator representing the end
 * of the key/value pair in the leaf node
 * @return : index iterator
 */
INDEX_TEMPLATE_ARGUMENTS
auto BPLUSTREE_TYPE::End() -> INDEXITERATOR_TYPE { 
  LeafPage* rightPage = this->FindEnd();
  return INDEXITERATOR_TYPE(rightPage,this->buffer_pool_manager_,rightPage->GetSize()); 
}

/**
 * @return Page id of the root of this tree
 */
INDEX_TEMPLATE_ARGUMENTS
auto BPLUSTREE_TYPE::GetRootPageId() -> page_id_t { return this->root_page_id_; }

INDEX_TEMPLATE_ARGUMENTS
void BPLUSTREE_TYPE::SetRootPageId(page_id_t rootId){
  this->root_page_id_ = rootId;
}

/*****************************************************************************
 * UTILITIES AND DEBUG
 *****************************************************************************/
/*
 * Update/Insert root page id in header page(where page_id = 0, header_page is
 * defined under include/page/header_page.h)
 * Call this method everytime root page id is changed.
 * @parameter: insert_record      defualt value is false. When set to true,
 * insert a record <index_name, root_page_id> into header page instead of
 * updating it.
 */
INDEX_TEMPLATE_ARGUMENTS
void BPLUSTREE_TYPE::UpdateRootPageId(int insert_record) {
  auto *header_page = static_cast<HeaderPage *>(buffer_pool_manager_->FetchPage(HEADER_PAGE_ID));
  if (insert_record != 0) {
    // create a new record<index_name + root_page_id> in header_page
    header_page->InsertRecord(index_name_, root_page_id_);
  } else {
    // update root_page_id in header_page
    header_page->UpdateRecord(index_name_, root_page_id_);
  }
  buffer_pool_manager_->UnpinPage(HEADER_PAGE_ID, true);
}

/*
 * This method is used for test only
 * Read data from file and insert one by one
 */
INDEX_TEMPLATE_ARGUMENTS
void BPLUSTREE_TYPE::InsertFromFile(const std::string &file_name, Transaction *transaction) {
  int64_t key;
  std::ifstream input(file_name);
  while (input) {
    input >> key;

    KeyType index_key;
    index_key.SetFromInteger(key);
    RID rid(key);
    Insert(index_key, rid, transaction);
  }
}
/*
 * This method is used for test only
 * Read data from file and remove one by one
 */
INDEX_TEMPLATE_ARGUMENTS
void BPLUSTREE_TYPE::RemoveFromFile(const std::string &file_name, Transaction *transaction) {
  int64_t key;
  std::ifstream input(file_name);
  while (input) {
    input >> key;
    KeyType index_key;
    index_key.SetFromInteger(key);
    Remove(index_key, transaction);
  }
}

/**
 * This method is used for debug only, You don't need to modify
 */
INDEX_TEMPLATE_ARGUMENTS
void BPLUSTREE_TYPE::Draw(BufferPoolManager *bpm, const std::string &outf) {
  if (IsEmpty()) {
    LOG_WARN("Draw an empty tree");
    return;
  }
  std::ofstream out(outf);
  out << "digraph G {" << std::endl;
  ToGraph(reinterpret_cast<BPlusTreePage *>(bpm->FetchPage(root_page_id_)->GetData()), bpm, out);
  out << "}" << std::endl;
  out.flush();
  out.close();
}

/**
 * This method is used for debug only, You don't need to modify
 */
INDEX_TEMPLATE_ARGUMENTS
void BPLUSTREE_TYPE::Print(BufferPoolManager *bpm) {
  if (IsEmpty()) {
    LOG_WARN("Print an empty tree");
    return;
  }
  ToString(reinterpret_cast<BPlusTreePage *>(bpm->FetchPage(root_page_id_)->GetData()), bpm);
}

/**
 * This method is used for debug only, You don't need to modify
 * @tparam KeyType
 * @tparam ValueType
 * @tparam KeyComparator
 * @param page
 * @param bpm
 * @param out
 */
INDEX_TEMPLATE_ARGUMENTS
void BPLUSTREE_TYPE::ToGraph(BPlusTreePage *page, BufferPoolManager *bpm, std::ofstream &out) const {
  std::string leaf_prefix("LEAF_");
  std::string internal_prefix("INT_");
  if (page->IsLeafPage()) {
    auto *leaf = reinterpret_cast<LeafPage *>(page);
    // Print node name
    out << leaf_prefix << leaf->GetPageId();
    // Print node properties
    out << "[shape=plain color=green ";
    // Print data of the node
    out << "label=<<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\" CELLPADDING=\"4\">\n";
    // Print data
    out << "<TR><TD COLSPAN=\"" << leaf->GetSize() << "\">P=" << leaf->GetPageId() << "</TD></TR>\n";
    out << "<TR><TD COLSPAN=\"" << leaf->GetSize() << "\">"
        << "max_size=" << leaf->GetMaxSize() << ",min_size=" << leaf->GetMinSize() << ",size=" << leaf->GetSize()
        << "</TD></TR>\n";
    out << "<TR>";
    for (int i = 0; i < leaf->GetSize(); i++) {
      out << "<TD>" << leaf->KeyAt(i) << "</TD>\n";
    }
    out << "</TR>";
    // Print table end
    out << "</TABLE>>];\n";
    // Print Leaf node link if there is a next page
    if (leaf->GetNextPageId() != INVALID_PAGE_ID) {
      out << leaf_prefix << leaf->GetPageId() << " -> " << leaf_prefix << leaf->GetNextPageId() << ";\n";
      out << "{rank=same " << leaf_prefix << leaf->GetPageId() << " " << leaf_prefix << leaf->GetNextPageId() << "};\n";
    }

    // Print parent links if there is a parent
    if (leaf->GetParentPageId() != INVALID_PAGE_ID) {
      out << internal_prefix << leaf->GetParentPageId() << ":p" << leaf->GetPageId() << " -> " << leaf_prefix
          << leaf->GetPageId() << ";\n";
    }
  } else {
    auto *inner = reinterpret_cast<InternalPage *>(page);
    // Print node name
    out << internal_prefix << inner->GetPageId();
    // Print node properties
    out << "[shape=plain color=pink ";  // why not?
    // Print data of the node
    out << "label=<<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\" CELLPADDING=\"4\">\n";
    // Print data
    out << "<TR><TD COLSPAN=\"" << inner->GetSize() << "\">P=" << inner->GetPageId() << "</TD></TR>\n";
    out << "<TR><TD COLSPAN=\"" << inner->GetSize() << "\">"
        << "max_size=" << inner->GetMaxSize() << ",min_size=" << inner->GetMinSize() << ",size=" << inner->GetSize()
        << "</TD></TR>\n";
    out << "<TR>";
    for (int i = 0; i < inner->GetSize(); i++) {
      out << "<TD PORT=\"p" << inner->ValueAt(i) << "\">";
      if (i > 0) {
        out << inner->KeyAt(i);
      } else {
        out << " ";
      }
      out << "</TD>\n";
    }
    out << "</TR>";
    // Print table end
    out << "</TABLE>>];\n";
    // Print Parent link
    if (inner->GetParentPageId() != INVALID_PAGE_ID) {
      out << internal_prefix << inner->GetParentPageId() << ":p" << inner->GetPageId() << " -> " << internal_prefix
          << inner->GetPageId() << ";\n";
    }
    // Print leaves
    for (int i = 0; i < inner->GetSize(); i++) {
      auto child_page = reinterpret_cast<BPlusTreePage *>(bpm->FetchPage(inner->ValueAt(i))->GetData());
      ToGraph(child_page, bpm, out);
      if (i > 0) {
        auto sibling_page = reinterpret_cast<BPlusTreePage *>(bpm->FetchPage(inner->ValueAt(i - 1))->GetData());
        if (!sibling_page->IsLeafPage() && !child_page->IsLeafPage()) {
          out << "{rank=same " << internal_prefix << sibling_page->GetPageId() << " " << internal_prefix
              << child_page->GetPageId() << "};\n";
        }
        bpm->UnpinPage(sibling_page->GetPageId(), false);
      }
    }
  }
  bpm->UnpinPage(page->GetPageId(), false);
}

/**
 * This function is for debug only, you don't need to modify
 * @tparam KeyType
 * @tparam ValueType
 * @tparam KeyComparator
 * @param page
 * @param bpm
 */
INDEX_TEMPLATE_ARGUMENTS
void BPLUSTREE_TYPE::ToString(BPlusTreePage *page, BufferPoolManager *bpm) const {
  if (page->IsLeafPage()) {
    auto *leaf = reinterpret_cast<LeafPage *>(page);
    std::cout << "Leaf Page: " << leaf->GetPageId() << " parent: " << leaf->GetParentPageId()
              << " next: " << leaf->GetNextPageId() << std::endl;
    for (int i = 0; i < leaf->GetSize(); i++) {
      std::cout << leaf->KeyAt(i) << ",";
    }
    std::cout << std::endl;
    std::cout << std::endl;
  } else {
    auto *internal = reinterpret_cast<InternalPage *>(page);
    std::cout << "Internal Page: " << internal->GetPageId() << " parent: " << internal->GetParentPageId() << std::endl;
    for (int i = 0; i < internal->GetSize(); i++) {
      std::cout << internal->KeyAt(i) << ": " << internal->ValueAt(i) << ",";
    }
    std::cout << std::endl;
    std::cout << std::endl;
    for (int i = 0; i < internal->GetSize(); i++) {
      ToString(reinterpret_cast<BPlusTreePage *>(bpm->FetchPage(internal->ValueAt(i))->GetData()), bpm);
    }
  }
  bpm->UnpinPage(page->GetPageId(), false);
}

template class BPlusTree<GenericKey<4>, RID, GenericComparator<4>>;
template class BPlusTree<GenericKey<8>, RID, GenericComparator<8>>;
template class BPlusTree<GenericKey<16>, RID, GenericComparator<16>>;
template class BPlusTree<GenericKey<32>, RID, GenericComparator<32>>;
template class BPlusTree<GenericKey<64>, RID, GenericComparator<64>>;

}  // namespace bustub
